package com.gxc.array;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 *  503. 下一个更大元素 II
 *  给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），
 *  返回 nums 中每个元素的 下一个更大元素 。
 *  数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，
 *  这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
 */
public class NextGreaterElements {

    public static void main(String[] args) {
        int[] nums = {5,4,3,2,1};

        println(handle(nums));
        println(handle2(nums));
    }

    private static int[] handle(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = -1;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            j = i+1;
            if (j == nums.length) {
                j = 0;
            }
            while (j!=i) {
                if (nums[j]>nums[i]) {
                    res[i] = nums[j];
                    break;
                }
                j++;
                if (j == nums.length) {
                    j = 0;
                }
            }
        }
        return res;
    }

    private static int[] handle2(int[] nums) {
        int n = nums.length;
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        //记录 下标 （下标包含的内容更多，下标可以获得实际位置的value）
        Stack<Integer> stack = new Stack<>();

        //复制该序列的前 n−1 个元素拼接在原序列的后面
        for (int i = 0; i < 2*n -1 ; i++) {
            while (!stack.isEmpty() && nums[i%n]>nums[stack.peek()]) {
                res[stack.pop()] = nums[i%n];
            }
            stack.push(i%n);
        }
        return res;
    }

    private static void println(int[] res) {
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i]);
            System.out.print(" ");
        }
        System.out.println("");
    }

    /**
     * 官方解
     * 单调栈+循环数组
     * 但是注意到只遍历一次序列是不够的，例如序列 [2,3,1]，
     * 最后单调栈中将剩余 [3,1]，其中元素 [1] 的下一个更大元素还是不知道的。
     *
     * 一个朴素的思想是，我们可以把这个循环数组「拉直」，
     * 即复制该序列的前 n−1 个元素拼接在原序列的后面。这
     * 样我们就可以将这个新序列当作普通序列，用上文的方法来处理。
     */
    class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int n = nums.length;
            int[] ret = new int[n];
            Arrays.fill(ret, -1);
            Deque<Integer> stack = new LinkedList<Integer>();
            for (int i = 0; i < n * 2 - 1; i++) {
                while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                    ret[stack.pop()] = nums[i % n];
                }
                stack.push(i % n);
            }
            return ret;
        }
    }

}
